๐Ÿ’ก ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ(LCA)

@Seongukbaek Posted May 13, 2022 ยท Updated May 13, 2022 ยท 7 min read

๐Ÿงท ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ

Lowest Common Ancestor ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ํŠธ๋ฆฌ์—์„œ ๋‘ ์ •์ ์ด ๋งŒ๋‚˜๋Š” ์ตœ์ดˆ ๋ถ€๋ชจ ์ •์ ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ํŠธ๋ฆฌ ๋ฌธ์ œ์—์„œ ๊ณตํ†ต ์กฐ์ƒ์„ ์ฐพ์•„์•ผ ํ•˜๊ฑฐ๋‚˜, ์ •์ ๊ณผ ์ •์  ์‚ฌ์ด์˜ ์ด๋™๊ฑฐ๋ฆฌ ๋˜๋Š” ๋ฐฉ๋ฌธ๊ฒฝ๋กœ๋ฅผ ์ €์žฅํ•ด์•ผ ํ•  ๊ฒฝ์šฐ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

๐Ÿชš ๊ณผ์ •

ํ•ด๋‹น ์ •์ ์˜ depth ์™€ parent ๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค. ์œ„ ๊ทธ๋ฆผ์—์„œ์˜ depth ์™€ parent ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค.

[depth : ์ •์ ] 0 -> 1 1 -> 2, 3 2 -> 4, 5, 6, 7 int[] parent = {0, 1, 1, 2, 2, 3, 3}; class Main { // ์ •์  ๋ฒˆํ˜ธ๊ฐ€ 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค๊ณ  ๊ฐ€์ • // depth์™€ parent ์ดˆ๊ธฐํ™” static int[] depth = {0,1,1,2,2,2,2}; static int[] parent = {0,1,1,2,2,3,3}; public static void main(String[] args) { int node1 = 3; int node2 = 4; int LCA = 0; while(true){ if(depth[node1] == depth[node2]) { // depth๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ if(parent[node1] == parent[node2]) { // ๋ถ€๋ชจ๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ, LCA๋ฅผ ์ฐพ์Œ LCA = parent[node1]; break; } else { // ๋ถ€๋ชจ๊ฐ€ ๋‹ค๋ฅด๊ธฐ์— ์ƒ์œ„ ์ •์ ์œผ๋กœ ์ด๋™ node1 = parent[node1]; node2 = parent[node2]; } } else { // depth๊ฐ€ ๋‹ค๋ฅธ ๊ฒฝ์šฐ. ๋” ์ž‘์€ depth์˜ ์ •์ ์„ ์ƒ์œ„๋กœ ์ด๋™ if (depth[node1] > depth[node2]) { node1 = parent[node1]; } else { node2 = parent[node2]; } } } System.out.println("LCA is: " + LCA); } }

ํ•˜์ง€๋งŒ ์œ„ ๋ฐฉ์‹์€ 1์„ธ๋Œ€ ๋ถ€๋ชจ๋งŒ์„ ๋ฐ˜๋ณตํ•ด์„œ ์ฐพ์•„ ์˜ฌ๋ผ๊ฐ€๊ธฐ ๋•Œ๋ฌธ์— O(N)O(N) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ์ด๋ฅผ ๊ฐœ์„ ํ•˜๊ธฐ ์œ„ํ•ด "1, 2, 4, 8, ... ์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ๊ฐ€ ๋ˆ„๊ตฐ์ง€๋„ ๊ธฐ๋ก"ํ•˜์—ฌ ์‚ฌ์šฉํ•œ๋‹ค. ์ด๋Š” O(logN)O(logN) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

๐Ÿชš ๊ฐœ์„  ๊ณผ์ •

1์ฐจ์› parent ๋ฐฐ์—ด์„, 20,21,22,...2^0, 2^1, 2^2, ... ๋ถ€๋ชจ์˜ ์ •๋ณด๋„ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด 2์ฐจ์› parent ๋ฐฐ์—ด๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค.

  • parent[n][k] (n = Tree์˜ ์ •์  ์ˆ˜, k = log(n)์˜ ์˜ฌ๋ฆผ)

๋จผ์ € ์ฃผ์–ด์ง„ tree์™€ root๋ฅผ ๊ฐ€์ง€๊ณ , DFS๋ฅผ ์ˆ˜ํ–‰ํ•˜๋ฉด์„œ ๊ฐ ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋œ 1์„ธ๋Œ€ ๋ถ€๋ชจ์™€, ๊นŠ์ด ์ •๋ณด๋ฅผ ๊ตฌํ•œ๋‹ค.

int[][] parent = new int[n][k]; int[] depth = new int[n]; Arrays.fill(depth, -1); void dfs(int cur) { for (int next : adj[cur]) { if (depth[next] == -1) { parent[next][0] = cur; depth[next] = depth[cur] + 1; dfs(next); } } return; }

์ด์ œ ๊ตฌํ•œ 1์„ธ๋Œ€ ๋ถ€๋ชจ ์ •๋ณด๋ฅผ ์ด์šฉํ•ด, 21,22,...2^1, 2^2, ... ๋ถ€๋ชจ์˜ ์ •๋ณด๋ฅผ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค.

  • ํ˜„์žฌ๋ฅผ ๊ธฐ์ค€์œผ๋กœ 2(212^1)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ๋Š” "ํ˜„์žฌ์˜ 1(202^0)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ์˜ 1(202^0)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ"์ด๋‹ค.
  • ํ˜„์žฌ๋ฅผ ๊ธฐ์ค€์œผ๋กœ 4(222^2)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ๋Š” "ํ˜„์žฌ์˜ 2(212^1)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ์˜ 2(212^1)์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ"์ด๋‹ค.
  • ์ฆ‰, ํ˜„์žฌ๋ฅผ ๊ธฐ์ค€์œผ๋กœ 2k2^k์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ๋Š” ํ˜„์žฌ์˜ 2kโˆ’12^{k-1}์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ์˜ 2kโˆ’12^{k-1}์นธ ๋–จ์–ด์ง„ ๋ถ€๋ชจ์ด๋‹ค.
// max = logN์˜ ์˜ฌ๋ฆผ void connectParents() { for (int k = 1; k < max; k++) { for (int cur = 1; cur <= n; cur++) { parent[cur][k] = parent[parent[cur][k-1]][k-1]; } } }

์™„์„ฑ๋œ ์ •๋ณด๋ฅผ ์ด์šฉํ•˜์—ฌ, ์•„๋ž˜์˜ ๊ณผ์ •์œผ๋กœ LCA๋ฅผ ์ฐพ๋Š”๋‹ค.

  • ๋‘ ์ •์ ์˜ depth ๋ฅผ ๊ฐ™๋„๋ก ํ•œ๋‹ค.
  • ๋ถ€๋ชจ๊ฐ€ ๊ฐ™์€ ์ •์ ์— ๋„๋‹ฌํ•  ๋•Œ๊นŒ์ง€ ์œ„๋กœ ์ ํ”„ํ•œ๋‹ค.

๋จผ์ € ๋‘ ์ •์ ์˜ depth ๊ฐ€ ๊ฐ™๋„๋ก ํ•˜๊ธฐ ์œ„ํ•ด, ๋‘ ์ •์  ๊ฐ„์˜ depth ์ฐจ์ด๋ฅผ ๊ตฌํ•œ๋‹ค.

  • depth ์˜ ์ฐจ๊ฐ€ 3 ์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜๋ฉด, ์ ํ”„๋ฅผ 2์˜ ์ง€์ˆ˜๋กœ ํ•˜๊ธฐ์—, 3 ์„ 2์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•œ๋‹ค.

    • 3 -> 11(2) ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๊ณ , ์ด๋Š” 202^0์นธ์งœ๋ฆฌ 1๋ฒˆ, 212^1์นธ์งœ๋ฆฌ 1๋ฒˆ ์ ํ”„๋ฅผ ์˜๋ฏธํ•œ๋‹ค.
    • ๋งŒ์•ฝ ์ฐจ๊ฐ€ 11 ์ด๋ผ๋ฉด, 1011(2) ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๊ณ , ์ด๋Š” 202^0์นธ์งœ๋ฆฌ 1๋ฒˆ, 212^1์นธ์งœ๋ฆฌ 1๋ฒˆ, 232^3์นธ์งœ๋ฆฌ 1๋ฒˆ ์ ํ”„๋ฅผ ์˜๋ฏธํ•œ๋‹ค.
int getLCA(int u, int v) { // u๋ฅผ ๋” ๊นŠ์€ ์ •์ ์œผ๋กœ! if (depth[u] < depth[v]) swap(u, v); int diffDist = depth[u] - depth[v]; for (int i = 0; diffDist != 0; i++) { if (diffDist % 2 == 1) u = parent[u][i]; diffDist /= 2; } }

์ด์ œ depth ๊ฐ€ ๊ฐ™์•„์กŒ๊ณ , ๋ถ€๋ชจ๊ฐ€ ๊ฐ™์€ ์ •์ ์— ๋„๋‹ฌํ•  ๋•Œ๊นŒ์ง€ ๋‘ ์ •์ ์„ ํ•จ๊ป˜ ์ ํ”„ํ•  ๊ฒƒ์ด๋‹ค.

  • 2log(ํŠธ๋ฆฌ์˜ย ์ •์ ย ์ˆ˜ย n)์˜ย ์˜ฌ๋ฆผ2^{log(ํŠธ๋ฆฌ์˜\ ์ •์ \ ์ˆ˜\ n)์˜\ ์˜ฌ๋ฆผ} ๋งŒํผ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๊ธฐ์—, ํŠธ๋ฆฌ์˜ ์ •์  ์ˆ˜๋ณด๋‹ค ๋” ํฐ ๋ฒ”์œ„์˜ ๋ถ€๋ชจ ์ •๋ณด๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ์ด๋Š” -1๋กœ ์ €์žฅ๋˜๋„๋ก ํ•œ๋‹ค. (๋ฉ”๋ชจ๋ฆฌ์˜ ๋‚ญ๋น„๋ฅผ ๋ง‰๊ธฐ ์œ„ํ•ด ์ตœ์ ํ™”๊ฐ€ ๊ฐ€๋Šฅํ•  ๊ฒƒ)
  • ํฐ ๋ฒ”์œ„์˜ ๋ถ€๋ชจ๋ถ€ํ„ฐ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ (16, 8, 4, 2, 1) ๋ถ€๋ชจ ์ •๋ณด๋ฅผ ํ™•์ธํ•˜๋ฉด์„œ ์ ํ”„ํ•œ๋‹ค.
  • ์œ„์—์„œ diffDist ๋งŒํผ ์ด๋™ํ–ˆ๋˜ ๊ฒƒ๊ณผ ๋น„์Šทํ•œ ๋ฐฉ์‹์œผ๋กœ ์ˆ˜ํ–‰ํ•˜๋Š”๋ฐ, ๋„์ฐฉ์ง€๋Š” LCA ๋ฐ”๋กœ ๋ฐ‘์˜ ์ž์‹์ด๋ผ๊ณ  ๊ฐ€์ •ํ•œ๋‹ค.

    • ์ ํ”„ํ–ˆ๋Š”๋ฐ, ๋‘ ์ •์ ์˜ ๋ถ€๋ชจ๊ฐ€ ๋™์ผํ•˜๋‹ค๋ฉด, ๋„์ฐฉ์ง€๋ฅผ ๋„˜์–ด๋ฒ„๋ฆฐ ๊ฒฝ์šฐ์ด๊ณ ,
    • ๋ถ€๋ชจ์˜ ๊ฐ’์ด -1์ด๋ผ๋ฉด ํŠธ๋ฆฌ์˜ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚œ ๊ฒฝ์šฐ์ด๋‹ค.
int getLCA(int u, int v) { ... if (u != v) { // ์ ํ”„ ๊ฐ€๋Šฅํ•œ ์ตœ๋Œ€๋ถ€ํ„ฐ ์‹œ์ž‘ for (int i = max - 1; i >= 0; i--) { // -1์ด๋ผ๋ฉด ํŠธ๋ฆฌ์˜ ๋ฒ”์œ„ ๋ฐ–, ๋‘ ๋ถ€๋ชจ๊ฐ€ ๊ฐ™๋‹ค๋ฉด LCA๊ฐ€ ์•„๋‹˜(๋„์ฐฉ์ง€๋ฅผ ๋„˜์–ด๋ฒ„๋ฆฐ ๊ฒฝ์šฐ) // ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด ์ ํ”„๋ฅผ ์ˆ˜ํ–‰, LCA์˜ ๋ฐ”๋กœ ๋ฐ‘ ์ •์ ์œผ๋กœ ์ ํ”„ if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) { u = parent[u][i]; v = parent[v][i]; } } // LCA ๋ฐ”๋กœ ๋ฐ‘ ์ •์ ์œผ๋กœ ์ ํ”„ํ–ˆ๊ธฐ์—, 1์นธ ์œ„๊ฐ€ LCA u = parent[u][0]; } return u; }

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€